package 单调栈_上;

// 柱状图中最大的矩形
// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度
// 每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积
// 测试链接：https://leetcode.cn/problems/largest-rectangle-in-histogram

public class Code04_LargestRectangleInHistogram {

    public static int MAXN = 100001;

    // 存储数组的下标
    public static int[] stack = new int[MAXN];

    public static int r;

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        r = 0;
        int ans = 0;
        // 遍历阶段
        for(int i = 0, cur; i < n; i++){
            while (r > 0 && heights[stack[r-1]] >= heights[i]){
                cur = stack[--r];
                int left = r == 0 ? -1 : stack[r-1];
                ans = Math.max(ans, heights[cur] * (i - left - 1));
            }
            stack[r++] = i;
        }
        // 清算阶段
        while (r > 0){
            int cur = stack[--r];
            int left = r == 0 ? -1 : stack[r-1];
            ans = Math.max(ans, heights[cur] * (n - left - 1));
        }
        return ans;
    }
}
